package com.yc.algorithm.leetcode;

import java.util.Set;

/**
 * 最长回文子串
 * Given a string s, return the longest palindromic substring in s
 * example1:
 *  Input: s = "babad"
 *  Output: "bab"
 *  Note: "aba" is also a valid answer.
 * example2:
 *  Input: s = "cbbd"
 *  Output: "bb"
 * example3:
 *  Input: s = "a"
 *  Output: "a"
 * example4:
 *  Input: s = "ac"
 *  Output: "a"
 */
public class LongestPalindrome {

//    public static void main(String[] args) {
////        String s = "babad";
//        String s = "cbbd";
//        System.out.println(longestPalindrome(s));
//    }

    public static String longestPalindrome(String s) {
        String res  = "";
        int max = 0, len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    res = s.substring(i, j);
                    max = Math.max(max, res.length());
                }
            }
        }
        return res;
    }

    public static boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;

    }


}
